class Solution {
public:
    vector<int> father;
    int find(int x){
        if(x != father[x]){
            father[x] = find(father[x]);
        }
        return father[x];
    }
    void Union(int u,int v){
        int x = find(u);
        int y = find(v);
        if(x == y) return;
        if(x > y){
            swap(x,y);
        }
        father[y] = x;
    }
    
    bool hasValidPath(vector<vector<int>>& grid) {
        int m = grid.size();
        int n = grid[0].size();
        father.resize(m*n);
        
        for(int i = 0;i < m*n;i++){
            father[i] = i;
        }
        
        for(int i = 0;i < m;i++){
            for(int j = 0;j < n;j++){
                int index = i*n+j;
                if(grid[i][j] == 1 || grid[i][j] == 3 || grid[i][j] == 5){
                    if(j > 0 && (grid[i][j-1] == 1 || grid[i][j-1] == 4 || grid[i][j-1] == 6)){
                        Union(index,index-1);
                    }
                }
                if(grid[i][j] == 2 || grid[i][j] == 6 || grid[i][j] == 5){
                    if(i > 0 && (grid[i-1][j] == 2 || grid[i-1][j] == 3 || grid[i-1][j] == 4)){
                        Union(index,index-n);
                    }
                }
            }
        }
        return find(m*n-1) == 0 ? true : false;
    }
};
